package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/31 11:53
 * @description :https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
 */
public class 剑指_41_数据流中的中位数 {
    @Test
    public void test() {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        System.out.println(medianFinder.findMedian());
    }


    class MedianFinder {
        Queue<Integer> A, B;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            A = new PriorityQueue<>();//小顶堆
            B = new PriorityQueue<>((x, y) -> y - x);//大顶堆
        }

        public void addNum(int num) {
            if (A.size() != B.size()) {
                A.add(num);
                B.add(A.poll());
            } else {
                B.add(num);
                A.add(B.poll());
            }
        }

        public double findMedian() {
            return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : A.peek();
        }
    }

}
